// m

// 给定一个整数n，生成所有可能且有效的括号组合

// 解题思路：回溯算法
// 为了生成的括号组合是有效的，回溯的时候，使用一个标记变量symbol来表示是否当前组合是否成对匹配
// 如果在当前组合中增加一个(,则symbol+1，如果增加一个)，则symbol-1，只有在symbol<n的时候才能增加(，在symbol>0的时候才能增加）
// 如果最终生成2*n的括号组合，并且symbol===0，则说明当前组合是有效的，将其加入到最终答案数组中

function generateParenthesis(n) {
    let parentheses = []
    function backtrack(parenthesis, symbol, index) {
        if (n * 2 === index) {
            if (symbol === 0) {
                parentheses.push(parenthesis) 
            }
        } else {
            if (symbol < n) {
                backtrack(parenthesis + '(', symbol + 1, index + 1)
            }
            if (symbol > 0) {
                backtrack(parenthesis + ')', symbol - 1, index + 1)
            }
        }
    }
    backtrack('', 0, 0)
    return parentheses
}

let n = 3 
console.log(generateParenthesis(n))